Hashing is a core operation in most online databases, like a library catalogue or an e-commerce website. A hash function generates codes that directly determine the location where data would be stored. So, using these codes, it is easier to find and retrieve the data. However, because traditional hash functions generate codes randomly, sometimes two pieces of data can be hashed with the same value. This causes collisions -- when searching for one item points a user to many pieces of data with the same hash value.

CAMBRIDGE, MA -- March 14, 2023 -- Researchers from MIT and other institutions report that a "hash function" -- a core database search operation -- can be significantly accelerated through the use of machine learning. The hope is that the new technique could accelerate computational systems that scientists use to store and analyze DNA, amino acid sequences, or other biological information. Hashing is used in applications from database indexing to data compression to cryptography. A hash function generates codes that directly determine the location where data would be stored. But because traditional hash functions generate codes randomly, sometimes two pieces of data can be hashed with the same value.

In this paper we improve solving two-player games by computing the game-theoretical value of every reachable state. A graphics processing unit located on the graphics card is used as a co-processor to accelerate the solution process. We exploit perfect hash functions to store the game states efficiently in memory and to transfer their ordinal representation between the host and the graphics card. As an application we validate Gasser's results that Nine-Men-Morris is a draw on a personal computer. Moreover, our solution is strong, while for the opening phase Gasser only provided a weak solution.

This paper exploits parallel computing power of graphics cards to accelerate state space search. We illustrate that modern graphics processing units (GPUs) have the potential to speed up breadth-first search significantly. For a bitvector representation of the search frontier, GPU algorithms with one and two bits per state are presented. Efficient perfect hash functions and their inverse are explored in order to achieve enhanced compression. We report maximal speed-ups of up to a factor of 27 wrt. single core CPU computation.